1. Field of the Invention
This invention relates to queuing systems, and more particularly to priority queue methods and apparatus in communication systems such as Universal Serial Bus systems, including wireless USB systems.
2. Background of the Related Art
Generally speaking, data to be transmitted (or received) is often passed through a transmit (or receive) queue. Once in a queue, data is generally transmitted in queue order.
In systems passing various types of data (e.g., voice, data, streaming video, etc.), data passing through the queue is given different priorities in an effort to transmit the highest priority data more quickly. One technique for ensuring that data of all priorities gets transmitted (or received) at a desired speed is to provide multiple queues, one for each priority level. In systems that do not offer multiple queues to support multiple priority class traffic scenarios, a boundary condition is effectively placed on the system software or driver requiring that in the transmit direction the software apply a minimum packet queuing strategy in the available system host transmit buffers in systems that want to establish multiple-class priority traffic scenarios. (Transmit being defined as packets from local system memory that traverse through the system out onto the medium. Receive is defined as incoming packets from the medium that are demodulated and placed into system memory.) This requirement is placed on the system in an effort to prevent a potentially large delay situation when a high priority packet is passed down to the driver from the operating system. The underlying assumption or solution is that such a priority frame cannot easily be ‘inserted’ in the existing queue, because the potential ownership or consumption of that available buffer is unknown (i.e., may have already been relinquished to the device already).
Quality of Service (QoS) is an all-encompassing phrase that denotes that different types of communications traffic are treated differently. In telecommunications systems, QoS is typically tied to voice and video services where users, who are accustomed to using the telephone, expect high quality voice (because historically, voice was considered the money maker and therefore that traffic received priority). In data communications systems, QoS is typically tied to multi-media services. In this context, multi-media refers to data systems that handle all kinds of data streams (‘streaming services’) that require no ‘automatic’ priority or re-transmission if a data packet is somehow lost in real-time.
Telecom systems are inherently stream oriented whereas data streams are inherently ‘bursty’ in nature. In the circuit switched world of telecom systems, ‘control’ is the model solution for all problems. This ‘control’, however, is fine for constant rate applications like voice and video where prediction of future is easy but loses some efficiency when handling data communications. On the other hand, data systems are complex and contain mixes of data sources and sinks called applications. Breaking data streams into packets makes it possible to serve many sources efficiently by multiplexing many data streams; the price of doing this, however, is in the form of delay. In many instances the application needs to bound or at the very least minimize this delay component, whereas some applications are immune to delivery latencies (herein referred to as ‘best-effort’ delivery.
Wireless systems also add a second level of uncertainty (and hence potential delay) in that the traffic flows are unpredictable in no small part due to the unpredictability of the radio links as well as external interference sources. Thus, use of rigid controls to manage traffic classes in wireless LANs can cause problems.
Universal Serial Bus (USB) is a popular standard for personal computer (PC) peripheral devices because of its versatile peripheral interconnection specifications. USB not only provides simplified hardware connectors but also provides support for various bus traffic, such as isochronous and bulk transfer activities. Although the USB specifications do provide a way for users to specify the upper bound on the number of bytes for each data transfer in a 1 millisecond (mS) time frame, little work has been done within the industry to provide QoS guarantees for devices (e.g., the lower bound on the bytes for each device type in a 1 mS time frame) and a mechanism in enforcing those guarantees.
Conventional methods are generally employed at the Kernel level or via hardware to implement and reserve both “Bulk” and “Isoch” pipes for support. However, such conventional methods have several problems, including increased complexity, increased silicon area, and requiring separate and distinct buffers for each ‘pipe’, all of which leads to increased overall costs. Generally, too, the conventional solutions address only a 2-tiered priority strategy: high priority and non-priority data traffic classes. A key requirement in QoS-managed systems is that all devices have to implement a given model and policy and not play ‘rogue’.
In present communications systems, transmit packets flow from host memory to an internal transmit buffer (e.g., a transmit packet buffer) usually under the control of a resident data movement or DMA engine, which in turn is commanded by the system driver or software. The Media Access Controller (MAC) retrieves transmit data from this packet buffer, frames it appropriately, and forwards it to a physical network layer. Likewise, receive packets flow to the MAC from the receiver. The MAC extracts packet data from surrounding header and CRC, while packet management logic determines whether each packet should be discarded, buffered, or merely decoded for network flow control and power management. Each packet which reaches the receive buffer is forwarded to the host computer via a data movement engine, again operating under host driver control. Generally, the functional implementation of on-device buffers limits the number of physical data that can be brought onto the device—i.e., packet memory is generally limited due to cost and area concerns.
FIG. 6 shows a block diagram of a conventional non-priority based management system in a media access controller (MAC).
In particular, FIG. 6 shows that in these present communication systems, packets are sequentially queued and managed on a ‘best-effort’ basis.
In non-priority managed system offerings, generally a single queuing structure is used to buffer up packets at the system level. Using this strategy when priority traffic is available, however, a boundary condition is effectively placed on the device driver requiring that in either the Tx or Rx directions, the software apply a minimum packet queuing strategy to the available buffer. This requirement is placed on the system in an effort to prevent a potential large delay situation when a high priority packet is passed down to the driver. This underlying assumption is that such a priority frame cannot easily be ‘inserted’ in the existing queue, because it is unknown if the ownership of the available buffer has been relinquished to the device already.
There is a need for a fair and efficient queuing method and apparatus useful in USB type systems, particularly in wireless USB systems.